package leetcode.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//120. 三角形最小路径和
public class MinimumTotal {


    public static void main(String[] args) {
        List<List<Integer>> lists = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>();
        list.add(2);
        list2.add(3);
        list2.add(4);
        lists.add(list);
        lists.add(list2);
        System.out.println(lists.toString());
        System.out.println(minimumTotal3(lists));

    }

    //从下到上的顺序 --dp
    public static int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] f = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                f[j] = Math.min(f[j], f[j + 1]) + triangle.get(i).get(j);
            }
        }
        return f[0];
    }

    //递归--从上到下  超时
    public static int minimumTotal2(List<List<Integer>> triangle) {
        return dfs(triangle, 0, 0);
    }

    private static int dfs(List<List<Integer>> triangle, int i, int j) {
        if (i == triangle.size()) {
            return 0;
        }
        return Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j);
    }

    //递归+二维数组记忆化--从上到下
    public static int minimumTotal3(List<List<Integer>> triangle) {
        int[][] memo = new int[triangle.size()][triangle.size()];
        return dfs2(triangle, 0, 0, memo);
    }

    private static int dfs2(List<List<Integer>> triangle, int i, int j, int[][] memo) {
        if (i == triangle.size()) {
            return 0;
        }
        if (memo[i][j] != 0) {
            return memo[i][j];
        }
        for (int m = 0; m < memo.length; m++) {
            for (int n = 0; n < memo[0].length; n++) {
                System.out.print(memo[m][n] + "     ");
            }
            System.out.println();
        }
        return memo[i][j] = Math.min(dfs2(triangle, i + 1, j, memo), dfs2(triangle, i + 1, j + 1, memo)) + triangle.get(i).get(j);
    }
}
